Propriété caractéristique du PGCD

Propriété

Soit \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}\) non nuls. Soit \(d \in \mathbb{N}^\ast\) .

On a  \(d=\mathrm{PGCD}(a;b)\)  si, et seulement si, il existe \((a';b') \in \mathbb{Z}^2\) tel que \(\left\lbrace \begin{array}{l} a=a'd \\ b=b'd \\ \mathrm{PGCD}(a';b')=1. \end{array} \right.\)  

Démonstration

On procède par double implication.

\([\Rightarrow]\) On suppose que \(d=\mathrm{PGCD}(a;b)\) .
Ainsi  \(d\) divise \(a\) et \(b\) , donc il existe \((a';b') \in \mathbb{Z}^2\) tel que \(a=a'd\) et \(b=b'd\) .
De plus, comme \(d>0\) , 
\(\begin{align*} d=\mathrm{PGCD}(a;b)=\mathrm{PGCD}(a'd;b'd) =d \times \mathrm{PGCD}(a';b') \end{align*}\)  
et donc, en simplifiant par \(d\) , on a \(\mathrm{PGCD}(a';b')=1\) .

\([\Leftarrow]\) On suppose qu'il existe \((a';b') \in \mathbb{Z}^2\) tel que \(a=a'd\) , \(b=b'd\) et \(\mathrm{PGCD}(a';b')=1\) .
On a alors, comme \(d>0\) , 
\(\begin{align*} \mathrm{PGCD}(a;b)=\mathrm{PGCD}(a'd;b'd) =d \times \mathrm{PGCD}(a';b') =d \times 1 =d \end{align*}\)  
et donc \(d=\mathrm{PGCD}(a;b)\) .